﻿using System;
using System.Drawing;
using System.Collections.Generic;

namespace ProblemsSet
{
    public class Problem_147 : BaseProblem
    {
        public override object GetResult()
        {
            const int m = 47;
            const int n = 43;
     
            ulong sm = 0;
            var dct = new Dictionary<Point, long>();

            for (int i = 1; i <= m; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    var tmp = GetCount(ref dct, i, j);
                    sm += (ulong)tmp;
                }
            }
            return sm;
        }

        private long GetCount(ref Dictionary<Point, long> dct, int m, int n)
        {
            if (m == 1)
                return n*(n + 3)/2 - 1;
            if (n == 1)
                return m * (m + 3) / 2 - 1;
            if (m == n && n == 2)
                return 18;
            var pt = new Point(Math.Max(m, n), Math.Min(m, n));
            m = pt.X;
            n = pt.Y;
            if (dct.ContainsKey(pt))
                return dct[pt];
            long tmp = 0;
            for (int i = 1; i <= n-1;i++)
            {
                long x = 2*i;
                long y = 2*(n - i);
                for (long k = 1; k <= x; k++ )
                {
                    for (long l = 1; l <=y; l++)
                    {
                        if ((l + k) / 2 <= m)
                            tmp++;
                    }
                }
            }
            for (int i = 1; i <= n ; i++)
            {
                long x = 2 * (i - 1) + 1;
                long y = 2 * (n - i)+1;
                for (long k = 1; k <= x; k++)
                {
                    for (long l = 1; l <= y; l++)
                    {
                        if ((l + k+2) / 2 <= m)
                            tmp++;
                    }
                }
            }
            tmp += GetCount(ref dct, n, m-1) + m*n*(n + 1)/2;
            dct.Add(pt, tmp);
            return tmp;
        }

        public override string Problem
        {
            get
            {
                return @"In a 3x2 cross-hatched grid, a total of 37 different rectangles could be situated within that grid as indicated in the sketch.


There are 5 grids smaller than 3x2, vertical and horizontal dimensions being important, i.e. 1x1, 2x1, 3x1, 1x2 and 2x2. If each of them is cross-hatched, the following number of different rectangles could be situated within those smaller grids:

1x1: 1 
2x1: 4 
3x1: 8 
1x2: 4 
2x2: 18

Adding those to the 37 of the 3x2 grid, a total of 72 different rectangles could be situated within 3x2 and smaller grids.

How many different rectangles could be situated within 47x43 and smaller grids?";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 846910284;
            }
        }
    }
}
